package com.xsherl.leetcode.solution;

import cn.hutool.core.lang.Assert;
import com.xsherl.leetcode.utils.PrintUtils;

import java.util.Arrays;

public class FindPositionOfElementInSortedArray {

    /**
     * 先利用二分查找找到指定元素所在位置，在用中心拓展思维，拓展左边界和右边界，一直到边界元素不等于目标元素为止
     *
     * @param nums
     * 0 <= nums.length <= 10^5
     * -10^9<= nums[i] <= 10^9
     * nums是一个非递减数组
     * @param target
     * -10^9<= target<= 10^9
     */
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0){
            return new int[]{-1, -1};
        }
        int len = nums.length, left = 0, right = len - 1;
        int mid = -1;
        while (left <= right){
            mid = (left + right) / 2;
            int val = nums[mid];
            if (val < target){
                left = mid + 1;
            } else if (val > target){
                right = mid - 1;
            } else {
                break;
            }
        }
        if (left > right){
            return new int[]{-1, -1};
        }
        left = right = mid;
        while (left >= 0 && nums[left] == nums[mid]){
            left--;
        }
        while (right < len && nums[right] == nums[mid]){
            right++;
        }
        return new int[]{left + 1, right - 1};
    }

    public static void main(String[] args) {
        int[] nums = {5,7,7,8,8,10};
        int target = 8;
        int[] ints = new FindPositionOfElementInSortedArray().searchRange(nums, target);
        PrintUtils.println(ints);
        Assert.isTrue(Arrays.equals(ints, new int[]{3, 4}));
    }

}
